package com.imooc;

import java.util.Random;

public class QuickSort {
    private QuickSort() {

    }

    private static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int left, int right) {
        if (left >= right)
            return;
        int p = partition(arr, left, right);
        sort(arr, left, p - 1);
        sort(arr, p + 1, right);
        return;

    }

    private static <E extends Comparable<E>> int partition(E[] arr, int left, int right) {

        int p=(new Random()).nextInt(right - left + 1) + left;
        swap(arr, left, p);

        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (arr[i].compareTo(arr[left]) < 0) {
                j++;
                swap(arr, i, j);
            }
        }
        swap(arr, left, j);
        return j;
    }

    private static <E extends Comparable<E>> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] arr = {8, 9, 5, 13, 4, 5};
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
